package dynamic;

import org.junit.Test;

import utils.BracketUtils;

public class Ex64 {
    class Solution1 {
        public int minPathSum(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] f = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) f[i][j] = grid[0][0];
                    else if (i == 0) f[i][j] = f[i][j - 1] + grid[i][j];
                    else if (j == 0) f[i][j] = f[i - 1][j] + grid[i][j];
                    else f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
                }
            }
            return f[m - 1][n - 1];
        }
    }

    //如何输出路径？
    class Solution2{
        public int minPathSum(int[][] grid) {
            int m = grid.length, n = grid[0].length, top, left, sum = m + n;
            int[][] f = new int[m][n];
            int[] p = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) f[i][j] = grid[0][0];
                    else {
                        top = i > 0 ? f[i - 1][j] : Integer.MAX_VALUE;
                        left = j > 0 ? f[i][j - 1] : Integer.MAX_VALUE;
                        f[i][j] = Math.min(top, left) + grid[i][j];
                        //利用p数组记录这条路径的上一个节点
                        p[form2Dto1D(i, j, m)] = top < left ? form2Dto1D(i - 1, j, m) : form2Dto1D(i, j - 1, m);
                    }
                }
            }

            //m * n的矩阵，其路径的长度必定为sum = m + n
            int[][] path = new int[sum][2];
            path[sum - 1] = new int[]{m - 1, n - 1}; //路径的最后一个位置
            int idx = form2Dto1D(m - 1, n - 1, m);
            for (int i = sum - 2; i >= 0; i--){
                int t  = p[idx];//记录上一轮路径
                path[i] = from1Dto2D(t, m);
                idx = t;
            }

            //从1开始输出，0是无效输入
            for (int i = 1; i < path.length; i++) {
                System.out.println("第" + i + "步经过了点" + "( "
                + path[i][0] + ", " + path[i][1] + " )" + ", 其值为" + grid[path[i][0]][path[i][1]]);
            }
            return f[m - 1][n - 1];
        }

        public int form2Dto1D(int i, int j, int m) {
            return m * i + j;
        }

        public int[] from1Dto2D(int idx, int m) {
            int[] res = new int[2];
            res[0] = idx / m;
            res[1] = idx % m;
            return res;
        }
    }

    //按照从小到大顺序记录路径，不必逆序
    class Solution {
        public int minPathSum(int[][] grid) {
            int m = grid.length, n = grid[0].length, top, left, sum = m + n;
            int[][] f = new int[m][n];
            int[] p = new int[m * n];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i == m - 1 && j == n - 1) f[i][j] = grid[0][0];
                    else {
                        top = i < m - 1 ? f[i + 1][j] : Integer.MAX_VALUE;
                        left = j < n - 1 ? f[i][j + 1] : Integer.MAX_VALUE;
                        f[i][j] = Math.min(top, left) + grid[i][j];
                        //利用p数组记录这条路径的上一个节点
                        p[form2Dto1D(i, j, m)] = top < left ? form2Dto1D(i + 1, j, m) : form2Dto1D(i, j + 1, m);
                    }
                }
            }

            int idx = form2Dto1D(0, 0, m);
            //倒序的倒序就是顺序
            int end = form2Dto1D(m - 1, n - 1, m);
            int i = 0;
       
            while (idx < end) {
                int[] path = from1Dto2D(idx, m);
                System.out.println("第" + (i++) + "步经过了点" + "( "
                + path[0] + ", " + path[1] + " )" + ", 其值为" + grid[path[0]][path[1]]);
                idx = p[idx];
            }
            System.out.println("第" + (i++) + "步经过了点" + "( "
            + (m - 1) + ", " + (n - 1) + " )" + ", 其值为" + grid[m - 1][n - 1]);
            return f[0][0];
        }

        public int form2Dto1D(int i, int j, int m) {
            return m * i + j;
        }

        public int[] from1Dto2D(int idx, int m) {
            int[] res = new int[2];
            res[0] = idx / m;
            res[1] = idx % m;
            return res;
        }
    }

    @Test
    public void test() {
        int[][] nums = BracketUtils.to2DArray("[[1,3,1],[1,5,1],[4,2,1]]");
        BracketUtils.printArray(nums);
        Solution s = new Solution();
        System.out.println(s.minPathSum(nums));;
    }

    public static void main(String[] args) {
        
    }
}
